home *** CD-ROM | disk | FTP | other *** search
/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Stacks / Updates⁄New / TEXAS for BMUG / C progs / qndxr.2 ƒ / merge_files.2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-11-03  |  4.9 KB  |  184 lines  |  [TEXT/KAHL]
  1. /* file merge_files.c ...  870902-... ^z
  2.  * more functions to do the work of merging subindices together ...
  3.  * with buffering of inputs and outputs ...
  4.  */
  5.  
  6.  
  7.  
  8. #include <stdio.h>
  9. #include <unix.h>
  10. #include <storage.h>
  11. #include <strings.h>
  12. #include <ctype.h>
  13. #include <proto.h>
  14. #include "qndxr.2.h"
  15.  
  16.  
  17. /* function to do the real work of merging sorted k & p
  18.  * files into a single sorted file...
  19.  *
  20.  * Procedure is as follows:
  21.  *
  22.  *    Compare the current key records from each of the N files to be merged.
  23.  *    Take the smallest of the keys (or, if there is a tie, take the one
  24.  *    from the earlier file number) and write its pointer records out to
  25.  *    the *.p file for the next generation.  If the key is a new one, that
  26.  *    is, if it differs from the previous key, write out the previous key
  27.  *    word and the value for cumulative_counts to the *.k file, and reset
  28.  *    the previous key's value to that of the current key.  Then repeat
  29.  *    this whole procedure, until all the input files are exhausted.
  30.  *
  31.  *    The above works provided that we are careful in choosing the smallest
  32.  *    key and never let a file that has been exhausted (reached EOF) win a
  33.  *    comparison.  The function smallest_key does that properly below, since
  34.  *    a file that is at EOF has returned a NULL pointer for its key_rec...
  35.  *
  36.  *  For each file, the variable prev_cc[i] holds the previous value of
  37.  *    cumulative_counts for that file, so that we can determine how
  38.  *    many ptr_recs to write out by doing a simple subtraction.
  39.  *
  40.  * Buffer numbering scheme:  the Kth input file has zbuffer #K
  41.  *    for its keys and zbuffer #(K+n) for its pointers; the output
  42.  *    buffers are zbuffers #(2*n) for keys and #(2*n+1) for pointers.
  43.  */
  44.  
  45. void nway_merge_kpfiles (ink, inp, outk, outp, n)
  46.   FILE *ink[], *inp[], *outk, *outp;
  47.   register int n;
  48.   {
  49.     register int i;
  50.     KEY_REC *kr[NMERGE], prev_key;
  51.     long prev_cc[NMERGE], out_cc;
  52.     extern long zbufsiz;
  53.     char *strncpy();
  54.     
  55.     DEBUG ("--entering nway_merge_kpfiles with n=%d\n", n);
  56.     for (i = 0; i < n; ++i)
  57.         prev_cc[i] = 0;
  58.     out_cc = 0;
  59.     
  60.     for (i = 0; i < n; ++i)
  61.       {
  62.         create_zbuffer (i, zbufsiz, ink[i], sizeof(KEY_REC));
  63.         create_zbuffer (i + n, zbufsiz, inp[i], sizeof(long));
  64.       }
  65.     create_zbuffer (2 * n, zbufsiz, outk, sizeof(KEY_REC));
  66.     create_zbuffer (2 * n + 1, zbufsiz, outp, sizeof(long));
  67.     
  68.     for (i = 0; i < n; ++i)
  69.         kr[i] = (KEY_REC *)next_input_item (i);
  70.     
  71.     i = smallest_key (kr, n);
  72.     strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  73.     DEBUG ("--first key is %.28s\n", prev_key.kkey);
  74.  
  75.     while (merge_not_finished (kr, n))
  76.       {
  77.         i = smallest_key (kr, n);
  78.         if (zstrcmp (prev_key.kkey, kr[i]->kkey))
  79.           {
  80.             copy_key_rec (prev_key.kkey, out_cc, 2 * n);
  81.             strncpy (prev_key.kkey, kr[i]->kkey, KEY_LENGTH);
  82.           }
  83.         copy_ptr_recs (i + n, kr[i]->ccount - prev_cc[i], 2 * n + 1);
  84.         out_cc += kr[i]->ccount - prev_cc[i];
  85.         prev_cc[i] = kr[i]->ccount;
  86.         kr[i] = (KEY_REC *)next_input_item (i);
  87.       }
  88.     
  89.     copy_key_rec (prev_key.kkey, out_cc, 2 * n);
  90.     DEBUG ("--finished nway merge ... final key=%.28s\n", prev_key.kkey);
  91.     flush_zbuffer (2 * n);
  92.     flush_zbuffer (2 * n + 1);
  93.     for (i = 0; i < 2 * n + 2; ++i)
  94.         free_zbuffer (i);
  95.   }
  96.  
  97.  
  98. /* function to copy a chosen number of ptr_recs (longs) from one file
  99.  * to another ... used in merging two files by merge_kpfiles() above....
  100.  * revised and simplified to use zbuffers....870902 ... ^z
  101.  */
  102.  
  103. void copy_ptr_recs (inzbuf, count, outzbuf)
  104.   register int inzbuf, outzbuf;
  105.   register long count;
  106.   {
  107.     register long *inp, *outp;
  108.     char *next_input_item(), *next_output_item();
  109.  
  110.     for ( ; count > 0; --count)
  111.       {
  112.         inp = (long *)next_input_item (inzbuf);
  113.         outp = (long *)next_output_item (outzbuf);
  114.         *outp = *inp;
  115.       }
  116.   }
  117.  
  118.  
  119. /* function to write a key record including kkey (key word) and ccount
  120.  * (cumulative_count) to an output file...
  121.  */
  122.  
  123. void copy_key_rec (kkey, cc, outzbuf)
  124.   char *kkey;
  125.   long cc;
  126.   int outzbuf;
  127.   {
  128.     KEY_REC *outp;
  129.     char *strncpy(), *next_output_item();
  130.  
  131.     outp = (KEY_REC *)next_output_item (outzbuf);
  132.     strncpy (outp->kkey, kkey, KEY_LENGTH);
  133.     outp->ccount = cc;
  134.   }
  135.  
  136.  
  137. /* simple function to see if we are not yet finished with all of the input
  138.  * files coming in to the merge operation ... signified by at least one of
  139.  * the key pointers being non-NULL....
  140.  */
  141.  
  142. int merge_not_finished (kr, n)
  143.   KEY_REC *kr[];
  144.   register int n;
  145.   {
  146.     register int i;
  147.     
  148.     for (i = 0; i < n; ++i)
  149.         if (kr[i] != NULL)
  150.             return (TRUE);
  151.     
  152.     return (FALSE);
  153.   }
  154.  
  155.  
  156. /* function to determine the smallest of the n keys pointed to by the
  157.  * kr[] vector of pointers to KEY_RECs ... note that a NULL ptr ranks
  158.  * after any other...also note that in case of a tie, the smaller
  159.  * value of i is the one to return (for a stable merging sort)
  160.  */
  161.  
  162. smallest_key (kr, n)
  163.   KEY_REC *kr[];
  164.   register int n;
  165.   {
  166.     register int i, smallest;
  167.  
  168.     for (i = 0; i < n; ++i)
  169.         if (kr[i] != NULL)
  170.           {
  171.             smallest = i;
  172.             break;
  173.           }
  174.  
  175.     for (i = smallest + 1; i < n; ++i)
  176.         if (kr[i] != NULL)
  177.             if (zstrcmp (kr[smallest]->kkey, kr[i]->kkey) > 0)
  178.                 smallest = i;
  179.  
  180.     return (smallest);
  181.   }
  182.  
  183.  
  184.